package com.LeetCode;

import static java.lang.Math.min;

/**
 * Created by Aqc on 2017/8/27.
 * 最长回文串——Manacher's Algorithm马拉车算法O(n)
 * 解析见有道云
 */
public class ManacherClass {

    public static void main(String arg[]) {
        Manacher mc = new Manacher();
    }
}

class Manacher {
    private String word = "waabwswfd";//12321   waabwswfd

    Manacher() {
        //add"#"
        String str = "#";
        char[] ch = word.toCharArray();
        for (char c : ch) {
            str += String.valueOf(c);
            str += "#";
        }

        int[] p = new int[str.length()];
        int mx = 0;//最远涉及位置，即半径所在位置
        int id = 0;//回环中心
        int maxCenter = 0;
        int maxLong = 0;
        for (int i = 0; i < str.length(); i++) {
            p[i] = i > mx ? 0 : min(p[id * 2 - i], mx - i);//关键语句！！！！！！！！！！
            while (i - p[i] - 1 > 0 && i + p[i] + 1 < str.length() && str.charAt(i - p[i] - 1) == str.charAt(i + p[i] + 1))
                p[i]++;
            if (p[i] + i > mx) {
                mx = p[i] + i;
                id = i;
            }
            if (p[i] > maxLong) {
                maxLong = p[i];
                maxCenter = i;
            }
        }
        //System.out.println(maxLong+"    "+maxCenter);
        System.out.println(word.substring((maxCenter - maxLong) / 2, (maxCenter - maxLong) / 2 + maxLong));
    }
}
